Turing complet

En la teoria d'ordinadors reals i imaginaris, dels llenguatges de programació i d'altres sistemes lògics, un sistema Turing complet és aquell que té un poder computacional equivalent a la màquina universal de Turing. En altres paraules, el sistema i la màquina universal de Turing poden emular-se entre si.

Encara quan és físicament impossible que existeixin aquestes màquines a causa que requereixen emmagatzematge il·limitat i probabilitat zero d'error, de forma col·loquial la completesa de Turing s'atribueix a màquines físiques o llenguatges de programació que podrien ser universals si tinguessin emmagatzematge infinit i fossin absolutament fiables. La primera d'aquestes màquines va aparèixer en 1941: la Z3 de Konrad Zuse, que era controlada per programes. La seva universalitat, no obstant això, va ser demostrada molt de temps després per Raúl Rojas en 1998.^[1] En aquest sentit, tots els ordinadors moderns són també Turing complets.

La completesa de Turing és significativa, doncs, cada disseny plausible d'un dispositiu de computació, per més avançat que sigui (àdhuc els ordinadors quàntics), poden ser emulades per una màquina universal de Turing. Així, una màquina que pugui actuar com una màquina universal de Turing pot, en principi, fer qualsevol càlcul que qualsevol altre ordinador és capaç de fer (en altres paraules, és programable). No obstant això, no hi ha esforç d'escriure un programa per a la màquina o sobre el temps que pot prendre el càlcul.^{[NB 1]}

Hi ha la hipòtesi que l'Univers és Turing complet (vegeu implicacions filosòfiques en la Tesi de Church-Turing i en Física digital).

Vegeu l'article de Teoria de la computabilitat per a una llarga llista de sistemes que són Turing complets, així com diversos sistemes que són menys potents, i diversos sistemes teòrics que són encara més potents que la màquina universal de Turing.

Error de citació: Existeixen etiquetes <ref> pel grup «NB» però no s'ha trobat l'etiqueta <references group="NB"/> corresponent.